package com.cqs.leetcode.sort;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author lixiaowen
 * @create 2019-12-12
 */
public class TopKFrequentElements {


    static class StackSort{
        /**
         * 小根堆
         * @param nums
         * @param k
         * @return
         */
        public List<Integer> topKFrequent(int[] nums, int k) {
            //统计词频
            Map<Integer, Long> frequent = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(integer -> integer, Collectors.counting()));
            ArrayList<Map.Entry<Integer, Long>> list = new ArrayList<>(frequent.entrySet());
            Collections.sort(list, (o1, o2) -> (int)(o2.getValue() - o1.getValue()));
            System.out.println(list); int i = 5; list.get(i--);
            //堆的构建
            Set<Map.Entry<Integer, Long>> entries = frequent.entrySet();
            return buildStack(entries,k);
        }

        /**
         * 构建小顶堆
         *
         * @param entries
         */
        private List<Integer> buildStack(Set<Map.Entry<Integer, Long>> entries, int k){
            Map.Entry<Integer, Long>[] stack = new Map.Entry[k];
            int len = 0;
            Iterator<Map.Entry<Integer, Long>> iterator = entries.iterator();
            while (iterator.hasNext()){
                Map.Entry<Integer, Long> next =iterator.next();
                //词频排在第K大后面的丢弃
                if (len == k && next.getValue() <= stack[0].getValue()) continue;
                if (len < k){
                    //尾部插入上浮
                    stack[len++] = next;
                    flow(stack, len-1);
                }else{
                    stack[0] = next;
                    sink(stack,0,len - 1);
                }
            }
            List<Integer> list = new ArrayList<>();
            for (Map.Entry<Integer, Long> entry : stack) {
                list.add(entry.getKey());
            }
            return list;
        }

        private void flow(Map.Entry<Integer, Long>[] stack, int end){
            while (true){
                int top = (end - 1) /2;
                if (top < 0) return;
                if (stack[top].getValue() > stack[end].getValue()){
                    swap(stack,top,end);
                    end = top;
                }else {
                    break;
                }
            }
        }

        private void sink(Map.Entry<Integer, Long>[] stack,int top,final int end){
            while (true){
                int min = 2 * top + 1;
                if (min > end) return;
                if (min + 1 <= end && stack[min + 1].getValue() < stack[min].getValue()){
                    min = min + 1;
                }
                if (stack[top].getValue() > stack[min].getValue()){
                    //交换
                    swap(stack, top, min);
                    top = min;
                }else {
                    break;
                }
            }
        }

        private void swap(Map.Entry<Integer, Long>[] stack,int i, int j){
            Map.Entry<Integer, Long> tmp = stack[i];
            stack[i] = stack[j];
            stack[j] = tmp;
        }

        public static void main(String[] args) {
            int cnt = 200;
            int[] arrs = new int[cnt];
            for (int i = 0; i < cnt; i++) {
                arrs[i] = new Random().nextInt( cnt/2);
            }
            int n = 2;
            List<Integer> list = new StackSort().topKFrequent(arrs, n);
            System.out.println(list);
        }

    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> collect = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(i -> i))
                .entrySet().stream().collect(Collectors.toMap(e -> e.getKey(), v -> v.getValue().size()));

        Set<Map.Entry<Integer, Integer>> entries = collect.entrySet();
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(entries);
        Collections.sort(list,  (o1, o2) -> o2.getValue() - o1.getValue());

        List<Integer> result = new ArrayList<>(k);
        for (int i = 0; i < k ; i++) {
            result.add(list.get(i).getKey());
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arrs = {1,1,1,2,2,3};
        int cnt = 100;
        arrs = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            arrs[i] = new Random().nextInt( cnt/5);
        }
        int n = 2;
        List<Integer> list = new TopKFrequentElements().topKFrequent(arrs, n);
        System.out.println(list);
    }
}
